Search results for "Deterministic context-free grammar"

showing 5 items of 5 documents

Block-Deterministic Regular Languages

2001

We introduce the notions of blocked, block-marked and blockdeterministic regular expressions. We characterize block-deterministic regular expressions with deterministic Glushkov block automata. The results can be viewed as a generalization of the characterization of one-unambiguous regular expressions with deterministic Glushkov automata. In addition, when a language L has a block-deterministic expression E, we can construct a deterministic finite-state automaton for L that has size linear in the size of E.

Deterministic pushdown automatonDiscrete mathematicsDeterministic finite automatonNested wordDeterministic automatonDeterministic context-free grammarQuantum finite automataTwo-way deterministic finite automatonNondeterministic finite automatonComputer Science::Formal Languages and Automata TheoryMathematics
researchProduct

Quantum Pushdown Automata

2000

Quantum finite automata, as well as quantum pushdown automata were first introduced by C. Moore, J. P. Crutchfield [13]. In this paper we introduce the notion of quantum pushdown automata (QPA) in a non-equivalent way, including unitarity criteria, by using the definition of quantum finite automata of [11]. It is established that the unitarity criteria of QPA are not equivalent to the corresponding unitarity criteria of quantum Turing machines [4]. We show that QPA can recognize every regular language. Finally we present some simple languages recognized by QPA, two of them are not recognizable by deterministic pushdown automata and one seems to be not recognizable by probabilistic pushdown …

Discrete mathematicsNested wordComputer scienceDeterministic context-free grammarContext-free languagePushdown automatonNonlinear Sciences::Cellular Automata and Lattice GasesEmbedded pushdown automatonDeterministic pushdown automatonTuring machinesymbols.namesakeRegular languageDeterministic automatonProbabilistic automatonsymbolsQuantum finite automataAutomata theoryComputer Science::Formal Languages and Automata TheoryQuantum cellular automaton
researchProduct

Quantum Finite Multitape Automata

1999

Quantum finite automata were introduced by C. Moore, J. P. Crutchfield [4], and by A. Kondacs and J. Watrous [3]. This notion is not a generalization of the deterministic finite automata. Moreover, in [3] it was proved that not all regular languages can be recognized by quantum finite automata. A. Ambainis and R. Freivalds [1] proved that for some languages quantum finite automata may be exponentially more concise rather than both deterministic and probabilistic finite automata. In this paper we introduce the notion of quantum finite multitape automata and prove that there is a language recognized by a quantum finite automaton but not by deterministic or probabilistic finite automata. This …

Discrete mathematicsProbabilistic finite automataFinite-state machineNested wordComputer scienceDeterministic context-free grammarTimed automatonω-automatonNonlinear Sciences::Cellular Automata and Lattice GasesAutomatonMobile automatonNondeterministic finite automaton with ε-movesDeterministic finite automatonDFA minimizationRegular languageDeterministic automatonProbabilistic automatonContinuous spatial automatonAutomata theoryQuantum finite automataTwo-way deterministic finite automatonNondeterministic finite automatonComputer Science::Formal Languages and Automata TheoryQuantum cellular automaton
researchProduct

Complexity of probabilistic versus deterministic automata

2005

Finite-state machineNested wordTheoretical computer scienceDFA minimizationDeterministic automatonComputer scienceDeterministic context-free grammarAutomata theoryQuantum finite automataProbabilistic analysis of algorithms
researchProduct

Tally languages accepted by Monte Carlo pushdown automata

1997

Rather often difficult (and sometimes even undecidable) problems become easily decidable for tally languages, i.e. for languages in a single-letter alphabet. For instance, the class of languages recognizable by 1-way nondeterministic pushdown automata equals the class of the context-free languages, but the class of the tally languages recognizable by 1-way nondeterministic pushdown automata, contains only regular languages [LP81]. We prove that languages over one-letter alphabet accepted by randomized one-way 1-tape Monte Carlo pushdown automata are regular. However Monte Carlo pushdown automata can be much more concise than deterministic 1-way finite state automata.

TheoryofComputation_COMPUTATIONBYABSTRACTDEVICESNested wordTheoretical computer scienceComputational complexity theoryComputer scienceDeterministic pushdown automatonTuring machinesymbols.namesakeRegular languageComputer Science::Logic in Computer ScienceQuantum finite automataNondeterministic finite automatonDiscrete mathematicsFinite-state machineDeterministic context-free languageComputabilityDeterministic context-free grammarContext-free languagePushdown automatonAbstract family of languagesComputer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)Cone (formal languages)Embedded pushdown automatonUndecidable problemNondeterministic algorithmTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESDeterministic finite automatonsymbolsComputer Science::Programming LanguagesAlphabetComputer Science::Formal Languages and Automata Theory
researchProduct